#include <stdio.h>
#include <stdlib.h>

int *MergeSort(int *, int);

int main(void) {
	int N = 4;
	int *mas = (int *)malloc(sizeof(int)*N);
	for (int i = 0; i < N; i++) {
		mas[i] = rand() % 100;
		printf("%d ", mas[i]);
	}
	printf("\n");
	int * res = MergeSort(mas, N);
	free(mas);
	mas = res;
	for (int i = 0; i < N; i++) {
		printf("%d ", mas[i]);
	}
	printf("\n");
	free(mas);

}

int *MergeSort(int * mas, int N) {
	int m2 = N / 2;
	int m1 = N - m2;
	int *res = (int *)malloc(sizeof(int)*N);
	if (N <= 1) {
		res[0] = mas[0];
		return res;
	}
	int *s_mas1 = MergeSort(mas, m1);
	int *s_mas2 = MergeSort(mas + m1, m2);
	int k = 0;
	int j = 0;
	int i = 0;
	while (k < N) {
		if (i >= m1) {
			res[k] = s_mas2[j];
			k++;
			j++;
			continue;
		}
		if (j >= m2) {
			res[k] = s_mas1[i];
			k++;
			i++;
			continue;
		}
		if (s_mas1[i] < s_mas2[j]) {
			res[k] = s_mas1[i];
			i++;
		}
		else {
			res[k] = s_mas2[j];
			j++;
		}
		k++;
	}
	free(s_mas1);
	free(s_mas2);
	return res;


}